package 程序员面试金典;

import java.util.Stack;

/**
 * 面试题 03.05. 栈排序
 * 栈排序。 编写程序，对栈进行排序使最小元素位于栈顶。最多只能使用一个其他的临时栈存放数据，但不得将元素复制到别的数据结构（如数组）中。该栈支持如下操作：push、pop、peek 和 isEmpty。当栈为空时，peek 返回 -1。
 *
 * 示例1:
 *
 *  输入：
 * ["SortedStack", "push", "push", "peek", "pop", "peek"]
 * [[], [1], [2], [], [], []]
 *  输出：
 * [null,null,null,1,null,2]
 * 示例2:
 *
 *  输入：
 * ["SortedStack", "pop", "pop", "push", "pop", "isEmpty"]
 * [[], [], [], [1], [], []]
 *  输出：
 * [null,null,null,null,null,true]
 * 说明:
 *
 * 栈中的元素数目在[0, 5000]范围内。
 */
public class T03_05 {

    public static void main(String[] args) {

        SortedStack sortedStack = new SortedStack();
        sortedStack.push(1);
        sortedStack.push(2);
        sortedStack.peek();
        sortedStack.pop();
        sortedStack.peek();

    }

}

class SortedStack {

    Stack<Integer> stack = new Stack<>();  //主栈升序

    Stack<Integer> stackHelp = new Stack<>(); // 辅助栈降序

    public SortedStack() {

    }

    public void push(int val) {

        if (stack.isEmpty()||stack.peek()>=val){ //如果要存入的值小于等于栈顶的值 直接存入
            stack.add(val);
        }else {  //把主栈的数据向辅助栈中导入 判断大小 插入val

            pushValByHelpStack(stack,stackHelp,val);
        }

    }

    public void pop() {
        if (!stack.isEmpty())
            stack.pop();
    }

    public int peek() {
        if (!stack.isEmpty()){
            return stack.peek();
        }
        return -1;
    }

    public boolean isEmpty() {
        return stack.isEmpty();
    }

    /**
     * 比较val 和栈顶的大小 如果 val大于栈顶的值 就将栈顶的值放入辅助栈中 直到发现val<=stack.peek(); 将val的值 放入栈中 然后将辅助栈中的值 都返回来
     */
    private void pushValByHelpStack(Stack<Integer> stack,Stack<Integer> helpStack,int val){

        while (!stack.isEmpty()&&stack.peek()<val){
            helpStack.add(stack.pop());
        }

        stack.add(val);

        while (!helpStack.isEmpty()){
            stack.add(stackHelp.pop());
        }

    }

}